package club.xiaojiawei.binarytree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/11/22 9:35 PM
 * @question 116. 填充每个节点的下一个右侧节点指针
 * @description 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。
 * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
 * 初始状态下，所有 next 指针都被设置为 NULL。
 */
public class Connect116 {

    public static void main(String[] args) {
        Node root = new Node(1, new Node(2, new Node(4), new Node(5), null), new Node(3, new Node(6), new Node(7), null), null);
        Node result = connect(root);
        System.out.println(result);
    }

    /**
     * DFS+队列
     * @param root
     * @return
     */
    public static Node connect(Node root) {
        if (root == null){
            return null;
        }
        LinkedList<Node> queue = new LinkedList<>();
        queue.add(root);
        int size;
        Node pre;
        while ((size = queue.size()) > 0){
            pre = null;
            for (int i = 0; i < size; i++) {
                Node current = queue.pop();
                current.next = pre;
                pre = current;
                if (current.left != null){
                    queue.add(current.right);
                    queue.add(current.left);
                }
            }
        }
        return root;
    }

    /**
     * DFS+递归
     * @param root
     * @return
     */
    public static Node connect2(Node root) {
        dfs(root, 0, new ArrayList<>());
        return root;
    }

    public static void dfs(Node node, int depth, List<Node> list){
        if (node == null){
            return;
        }
        if (depth == list.size()){
            list.add(node);
        }else {
            node.next = list.get(depth);
            list.set(depth, node);
        }
        dfs(node.right, ++depth, list);
        dfs(node.left, depth, list);
    }

    /**
     * 民间-使用已建立的next 指针（递归版）（nb）
     * @param root
     * @return
     */
    public static Node connect3(Node root) {
        if(root == null){
            return null;
        }
        if(root.left != null){
            root.left.next = root.right;
            root.right.next = (root.next != null)? root.next.left : null;
            connect(root.left);
            connect(root.right);
        }
        return root;
    }

    /**
     * 官方-使用已建立的next 指针
     * @param root
     * @return
     */
    public static Node connect4(Node root) {
        if (root == null) {
            return root;
        }
        // 从根节点开始
        Node leftmost = root;
        while (leftmost.left != null) {
            // 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针
            Node head = leftmost;
            while (head != null) {
                // CONNECTION 1
                head.left.next = head.right;
                // CONNECTION 2
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                // 指针向后移动
                head = head.next;
            }
            // 去下一层的最左的节点
            leftmost = leftmost.left;
        }
        return root;
    }

     static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;
        public Node() {}
        public Node(int _val) {
            val = _val;
        }
        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }
}
